`
https://leetcode.cn/problems/longest-well-performing-interval/
`

/**
 * @param {number[]} hours
 * @return {number}
 */
var longestWPI = function (hours) {
  const n = hours.length

  // 将工作小时大于 8 的看作 1，小于等于 8 的看作 -1
  // 将问题等价为求和大于 0 的最长子数组的长度
  const prefix = new Array(n + 1)
  prefix[0] = 0
  for (let i = 1; i < prefix.length; i++) {
    prefix[i] = prefix[i - 1] + (hours[i - 1] > 8 ? 1 : -1)
  }

  let res = 0

  const valToIdx = new Map()
  for (let i = 1; i < prefix.length; i++) {
    if (!valToIdx.has(prefix[i])) {
      valToIdx.set(prefix[i], i)
    }

    // 如果当前前缀和大于 0 ，说明从开始到现在的整个区间都是符合条件的
    if (prefix[i] > 0) {
      res = Math.max(res, i)
    } else {
      // 当前前缀和小于或等于 0，则需要找到一个数能补到大于 0，使其符合结果
      // 这个数便是当前前缀和减 1，例如当前前缀和为 -1，则需要 -1 - (-2) 才会大于 0，符合结果
      if (valToIdx.has(prefix[i] - 1)) {
        res = Math.max(res, i - valToIdx.get(prefix[i] - 1))
      }
    }
  }
  
  return res
};